{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "operational-productivity",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, low, high, x):\n",
    "    # coppyed\n",
    "    if high >= low:\n",
    "        mid = (high + low) // 2\n",
    "        if arr[mid] == x:\n",
    "            return mid\n",
    "        # If element is smaller than mid, then it can only\n",
    "        # be present in left subarray\n",
    "        elif arr[mid] > x:\n",
    "            return binary_search(arr, low, mid - 1, x)\n",
    "        # Else the element can only be present in right subarray\n",
    "        else:\n",
    "            return binary_search(arr, mid + 1, high, x)\n",
    "    else:\n",
    "        # Element is not present in the array\n",
    "        return high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "cosmetic-terrorist",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1,4,7,9,20,55]\n",
    "binary_search(arr, 0, len(arr), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "swedish-sigma",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1,4,7,7,7,9,20,55]\n",
    "binary_search(arr, 0, len(arr)-1, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "immune-hollywood",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/most-profit-assigning-work\n",
    "\n",
    "\n",
    "Runtime: 7212 ms, faster than 5.16% of Python3 online submissions for Most Profit Assigning Work.\n",
    "Memory Usage: 17.8 MB, less than 6.14% of Python3 online submissions for Most Profit Assigning Work.\n",
    "\n",
    "\n",
    "```python\n",
    "def binary_search(arr, low, high, x):\n",
    "    # coppyed\n",
    "    if high >= low:\n",
    "        mid = (high + low) // 2\n",
    "        if arr[mid] == x:\n",
    "            while mid + 1 < len(arr):\n",
    "                if arr[mid+1] > x:\n",
    "                    return mid\n",
    "                mid += 1\n",
    "            return mid\n",
    "        # If element is smaller than mid, then it can only\n",
    "        # be present in left subarray\n",
    "        elif arr[mid] > x:\n",
    "            return binary_search(arr, low, mid - 1, x)\n",
    "        # Else the element can only be present in right subarray\n",
    "        else:\n",
    "            return binary_search(arr, mid + 1, high, x)\n",
    "    else:\n",
    "        # Element is not present in the array\n",
    "        return high\n",
    "    \n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        #6:39\n",
    "        length = len(difficulty)\n",
    "        info_arr = []\n",
    "        for index, _ in enumerate(difficulty):\n",
    "            info_arr.append((index, difficulty[index], profit[index]))\n",
    "        info_arr.sort(key=lambda tup: tup[1])\n",
    "        new_difficulty = [item[1] for item in info_arr]\n",
    "        new_profit = [item[2] for item in info_arr]\n",
    "        #print(new_difficulty)\n",
    "        #print(new_profit)\n",
    "        #print(list(sorted(worker)))\n",
    "        worker_dict = dict()\n",
    "        for wk in worker:\n",
    "            if wk in worker_dict:\n",
    "                worker_dict[wk] += 1\n",
    "            else:\n",
    "                worker_dict[wk] = 1\n",
    "        money = 0\n",
    "        #print(\"_______\")\n",
    "        for wk in sorted(worker_dict.keys()):\n",
    "            index = binary_search(new_difficulty, 0, length-1, wk)\n",
    "            if new_difficulty[index] <= wk:\n",
    "                #if index + 1 < length:\n",
    "                #    if new_difficulty[index+1] <= wk:\n",
    "                #        index += 1\n",
    "                money += max(new_profit[:index+1]) * worker_dict[wk]\n",
    "                #print(wk, max(new_profit[:index+1]))\n",
    "        return money\n",
    "        #7:44\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "hungry-youth",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}